package week_03;

import java.util.ArrayList;
import java.util.List;

public class FindCycleEdg_684 {
    private List<List<Integer>> edges = new ArrayList<>();
    private int n;
    private boolean hasCycle;
    private boolean[] visited;

    public int[] findRedundantConnection(int[][] inputs) {
        // input:[[1,2], [2,3], [3,4], [1,4], [1,5]]
        // output:[1,4]
        //找到边数—— 通过max（item）
        for (int i = 0; i < inputs.length; i++) {
            n = Math.max(inputs[i][0], inputs[i][1]);
        }
        //初始化好每个边的边组，下标是边号
        for (int i = 0; i < n + 1; i++) {
            edges.add(new ArrayList<>());
        }
        visited=new boolean[n+1];
        for (int i = 0; i < n + 1; i++) {
            visited[i] = false;
        }
        //迭代inputs ->dfs 查找是否有环
        hasCycle = false;
        for (int[] item : inputs) {
            int u = item[0];
            int v = item[1];
            addEdge(u, v);
            addEdge(v, u);
            dfs(u, -1);
            if (hasCycle) return new int[]{u, v};
        }
        return null;
    }

    public void dfs(int u, int parent) {
        visited[u] = true;
        for (int edge : edges.get(u)) {
            if (edge == parent) continue;
            if (visited[edge] == true) {
                hasCycle = true;
            }else{
                dfs(edge,u);
            }
        }
        visited[u]=false;
    }

    public void addEdge(int u, int v) {
        System.out.println(u+" "+v);
        edges.get(u).add(v);
    }
}
